// Boyer-Moore 投票算法 时间复杂度 O(n) 空间复杂度 O(1)

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int ans, count = 0;
        for (auto& num: nums) {
            if (count == 0) {
                ans = num;
                count++;
            }
            else if (ans == num) {
                count++;
            }
            else {
                count--;
            }
        }
        return ans;
    }
};